#include <cstdio>
#include <cstring>

#define MAXN 100+2
#define max(a,b) (a>b?a:b)

int MAP[MAXN][MAXN];

int main() {
	int kase;
	scanf("%d", &kase);
	while (kase--) {
		int n;
		scanf("%d", &n);
		memset(MAP, 0, sizeof(MAP));
		for (int i=0; i<n; i++) {
			for (int j=0; j<=i; j++) {
				scanf("%d", &MAP[i][j]);
			}
		}
		//DP
		for (int i=n-2; i>=0; i--) {
			for (int j=0; j<=i; j++) {
				MAP[i][j] = max(MAP[i][j]+MAP[i+1][j], MAP[i][j]+MAP[i+1][j+1]);
			}
		}
		printf("%d\n", MAP[0][0]);
	}
	return 0;
}
